package com.qezhhnjy.leetcode.question.tree;

import com.qezhhnjy.leetcode.entity.Node;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author qezhhnjy
 * @date 2020/12/18-22:49
 * <p>
 * 给定一个 N 叉树，返回其节点值的前序遍历。
 */
public class NTreePreOrderTraversal {

    List<Integer> result = new ArrayList<>();

    public List<Integer> preorder(Node root) {
        if (root == null) return null;
        result.add(root.val);
        if (root.children != null) {
            for (Node child : root.children) {
                preorder(child);
            }
        }
        return result;
    }

    public List<Integer> iteration(Node root) {
        if (root == null) return result;

        LinkedList<Node> stack = new LinkedList<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            Node poll = stack.pollLast();
            if (poll != null) {
                result.add(poll.val);
                Collections.reverse(poll.children);
                stack.addAll(poll.children);
            }
        }
        return result;
    }
}
